package l.l.w.CodingInterviews;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by llw on 2018/4/12/0012.
 *
 * 请实现一个函数用来找出字符流中第一个只出现一次的字符。
 * 例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。
 * 当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
 * 如果当前字符流没有存在出现一次的字符，返回#字符。
 *
 * 思路：时间复杂度O(1)，空间复杂度O(256)
 *      用一个256长度的数组，表示字符出现的次数。用一个队列表示字符出现的顺序
 *      插入时：
 *          遇到第一次出现的字符，则将出现次数计为 1，并将其加入队列尾部
 *          遇到多次出现的字符是，将出现次数加一
 *      访问时：
 *          如果队首的字符出现次数不为1，则弹出，直到遇到出现次数为1的字符（不弹出）。
 *          若队列为空，则返回 #
 *
 */
public class 字符流中第一个不重复的字符 {
    int[] chars = new int[256];
    Queue<Character> queue = new LinkedList<Character>();

    public void Insert(char ch){
        if(chars[ch] == 0){
            queue.add(ch);
            chars[ch] = 1;
        }else{
            chars[ch] = chars[ch] + 1;
        }
    }
    public char FirstAppearingOnce(){
        while(!queue.isEmpty()){
            char c = queue.peek();
            if(chars[c] > 1){
                queue.poll();
            }else{
                return c;
            }
        }
        return '#';
    }

    public static void main(String[] args) {
        String str = "googlel";
        字符流中第一个不重复的字符 obj = new 字符流中第一个不重复的字符();
        for(int i = 0; i < str.length(); ++i){
            obj.Insert(str.charAt(i));
            System.out.println(obj.FirstAppearingOnce());
        }
    }
}
